[POVRay developers, please make sure to read part 2.3.]

Okay, let's come straightly to the point: 

Rendering complicated scenes can take ages, especially if you render 
animations. While this is often acceptable for the final rendering, it 
really has potential for improvement if you're just interested in 
a preview during modelling. 

Often, degrading quality (+Q0) is not an option because e.g. you need 
the shadow to better view the object orientation in space, etc. 

So, let's discuss a different idea (which I do not claim credit 
for [1]): 

The principle is to only render some pixels and calculate the color of 
other pixels using interpolation. 

I read some papers which indicate that (if done properly) speed can be 
increased by an order of magnitude while nearly not affecting quality 
(depending on the scene, of course). The stuff in question is called 
Directional Coherence Map.   [ Wow. Sounds cool, right? ;) ]

My first question is: Is somebody working on that for POVRay? 
Are there patches addressing this issue?

Being a passionate C/C++ programmer I thought that it is probably no 
good idea to wait until the POV Ray team implements something like that. 
So, I had a look at the source code myself two days ago. 

Let's come to the points which have to be discussed: 


1. (Mosaic) Preview: 

The current mosaic preview adds rendering time because the pixels 
rendered in the preview are not used in the final rendering. 
So, I think, one could use a fixed-grid (e.g. 8x8) bilinearly 
interpolated preview instead. This should be sufficient for a quick 
view of the image before actually rendering it and would produce 
nicer images than an 8x8 mosaic preview. 

I implemented that and it works fine. 


2. Actual image rendering:

The more interesting part. 
The easiest approch is to render every 8th pixel in X and Y direction. 
4 pixels ( (x,y), (x+8,y), (x,y+8), (x+8,y+8) ) build a block. If 
these four pixel differ less (in color) than a specified threshold, 
the whole 8x8 block is evaluated using bilinear interpolation. 

Else, the block is divided into 4 blocks of size 4x4 requiring that 
5 more pixels are rendered. Then, you subdivide into 2x2 and finally 
you render all the left pixels. 

This is what I implemented yesterday. To keep mem usage low, I am 
using a buffer of 9 image lines. The pixels rendered during the 
preview are stored in a separate width/8 x height/8 buffer and 
being re-used. [Dumb algo? - Read 2.3.]

However, there are several issues: 

2.1. First, the povray code structure: 

Some easy modifications would have to made (better control when 
plot_pixel() actually calls XPutImage() by adding a plot_flush(x,y,w,h) 
function, etc). 

More seriuos are: 

Prune_Vista_Tree()
  I don't know if it is speed critical but it has to be called much 
  more often, because 8x8 blocks are rendered sequentially which means 
  that the Y coordinate changes freqently. 

Do_Cooperate(). 
  Don't know when it should be called or if it can cope with the 
  situation. Could someone enlighten me on POVMS? It seems to deal 
  with "messages", "queues" and "objects" but I have no clue. 

Current_Line_Number and Current_Line. 
  These are global vars and the latter is hard to grep because of 
  the similarity with the first one. I don't use them as I use my 
  own line buffer (9 lines). 

Field_Render_Flag:
  Seems to be some strange thing skipping odd or even lines.  
  Probably not 100% incompatible but I currently see no reason for 
  supporting it. Maybe anyone has arguments [explain why useful]. 

Antialiasing:
  Not supported but there is currently not much point in it as we 
  are talking about rendering more quickly. 


2.2. Evaluation order:

I am currently rendering a rough preview and then rendering the image 
top to bottom, 8 lines at a time. This requires "only" 
9*width*sizeof(COLOUR) bytes of buffer memory. 8x8 blocks are computed 
sequentially. 

The other idea would be to keep the whole image im memory and execute 
the stages of the algorithm sequentially on the complete image. Nicer 
to look at but requires much more RAM (6 Mb for 640x480). No 
possibility to resume a half-done image. 


2.3. The algorithm itself:

As you probably guessed, I only explained the first step of the 
algorithm. After evaluating the 4 corer pixels one could render a 
complete rectangle border (32 pixels). Then apply the directional 
coherence map. 

However, after having rendered the 4 corner pixels, the main problem 
is to decide on how to go on. Using a checker plane, I currently get 
ugly 8x8 alias effects; objects like thin cones can be skipped 
completely (which is extremely annoing in animations). 

One idea would be to save which object had most influence on the 
color of the ray. If the 4 corner pixels come from different objects, 
do not interpolate immediately. 

Obviously, textures don't work well with the algorithm because they 
behave like fine detail. [2] suggests applying them afterwards but 
I doubt that this is feasible for povray. OTOH, you normally don't 
use lots of textures if you render a preview. 

MOST CRITICAL is the detection if there is more than one object 
inside the 8x8 block. A routine doing a quick test on that would 
come quite handy. Problems may occur with partial reflection or  
interior (ior) etc. but returning (false) positives for some parts 
of the scene is acceptable. Unfortunately, I am not familiar with 
the innermost workings of the POVRay "engine" so help is appreciated. 

[Hope someone is still reading this.] 

Regards,
Wolfgang

References:

[1] Baining Guo, Progressive Radiance Evaluation Using Directional 
      Coherence Maps, SIGGRAPH '98 Proceedings


Source code of my patch is delivered on request and may be used 
under the POV license as well as under the GNU GPL. 
It is not limited to 8x8 blocks but I used that here for 
simplicity. It is work in progress and far from complete but if 
anyone wants to comment on it i'll be happy.

Post a reply to this message